package com.yangtao.prototype.common.tree;

import com.yangtao.framework.util.JsonUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * User: 杨涛
 * Date: 11-4-4
 * Time: 下午8:29
 */
public class TreeResolver {

	/**
	 * 将一个树状结构数组变为一个json字符串
	 *
	 * @param trees 树状结构数组
	 * @param <X>
	 * @return
	 */
	public static <X extends TreeNode> String toStoreString(List<X> trees) {
		return toStoreString(trees, null);
	}

	/**
	 * 将一个树状结构数组变为一个json字符串
	 *
	 * @param trees  树状结构数组
	 * @param rootId 根节点ID
	 * @param <X>
	 * @return
	 */
	public static <X extends TreeNode> String toStoreString(List<X> trees, String rootId) {
		List<X> resolvedTree = resolveTree(trees, rootId);
		return JsonUtil.obj2Json(resolvedTree, true);
	}

	/**
	 * 将平面结构的数据，变成立体结构的数据
	 *
	 * @param trees
	 */
	public static <X extends TreeNode> List<X> resolveTree(List<X> trees) {
		return resolveTree(trees, null);
	}

	/**
	 * 将平面结构的数据，变成立体结构的数据
	 *
	 * @param trees
	 */
	public static <X extends TreeNode> List<X> resolveTree(List<X> trees, String rootId) {
		List tree = new ArrayList();
		List<X> roots = getRootNode(trees, rootId);
		for (X root : roots) {
			addNode(root, trees);
			tree.add(root);
		}
		return tree;
	}

	private static <X extends TreeNode> List<X> getRootNode(List<X> trees, String rootId) {
		List<X> ret = new ArrayList<X>();
		for (int i = 0; i < trees.size(); i++) {
			X tree = trees.get(i);
			if ((rootId == null && tree.obtainParentId() == null)
					|| (rootId != null && rootId.equals(tree.obtainParentId()))) {
				ret.add(tree);
				trees.remove(i);
			}
		}
		return ret;
	}

	public static <X extends TreeNode> void addNode(TreeNode root, List<X> trees) {
		//System.out.println(trees.size());
		for (int i = 0; i < trees.size(); i++) {
			X tree = trees.get(i);
			if (tree.obtainParentId() != null && tree.obtainParentId().equals(root.obtainIdentity())) {
				root.obtainChildren().add(tree);
				//递归调用自身
				addNode(tree, trees);
			}
		}
	}

	public static String toJsonString(List<? extends TreeNode> trees) {
		return JsonUtil.obj2Json(trees, false);
	}

	/**
	 * 测试过滤节点的方法的功能和性能
	 * 经过测试，在2000个节点左右的时候，解析和序列化时间大概为600毫秒左右
	 * 在数据量扩大的时候，解析时间消耗非常快，序列化时间不变。
	 * 所以在大量数据的情况下需要优化解析算法
	 * 已经优化了算法
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		List<TestTree> trees = new ArrayList<TestTree>();
		int testCount = 100;
		for (int i = 0; i < testCount; i++) {
			TestTree tRoot = new TestTree("root" + i, "根节点一" + i, "root", 2, "a", null);
			TestTree tNode_1 = new TestTree("node_1" + i, "节点一" + i, "root", 2, "a", "root" + i);
			TestTree tNode_2 = new TestTree("node_2" + i, "节点二" + i, "root", 2, "a", "root" + i);
			TestTree tNode_3 = new TestTree("node_3" + i, "节点三" + i, "root", 2, "a", "root" + i);
			TestTree tNode_1_1 = new TestTree("node_1_1" + i, "节点一一" + i, "root", 2, "a", "node_1" + i);
			TestTree tNode_1_2 = new TestTree("node_1_2" + i, "根节点一二" + i, "root", 2, "a", "node_1" + i);
			TestTree tNode_1_3 = new TestTree("node_1_3" + i, "根节点一三" + i, "root", 2, "a", "node_1" + i);
			TestTree tNode_1_1_1 = new TestTree("node_1_1_1" + i, "节点一一一" + i, "root", 2, "a", "node_1_1" + i);
			TestTree tNode_1_1_2 = new TestTree("node_1_1_2" + i, "节点一一二" + i, "root", 2, "a", "node_1_1" + i);
			TestTree tNode_1_1_3 = new TestTree("node_1_1_3" + i, "节点一一三" + i, "root", 2, "a", "node_1_1" + i);
			TestTree tNode_1_1_4 = new TestTree("node_1_1_4" + i, "节点一一四" + i, "root", 2, "a", "node_1_1" + i);
			TestTree tNode_1_1_4_1 = new TestTree("node_1_1_4_1" + i, "节点一一四一" + i, "root", 2, "a", "node_1_1_4" + i);
			TestTree tNode_2_1 = new TestTree("tNode_2_1" + i, "根节点二一" + i, "root", 2, "a", "node_2" + i);
			TestTree tNode_2_2 = new TestTree("tNode_2_2" + i, "根节点二二" + i, "root", 2, "a", "node_2" + i);
			TestTree tNode_2_3 = new TestTree("tNode_2_3" + i, "根节点二三" + i, "root", 2, "a", "node_2" + i);
			TestTree tNode_3_1 = new TestTree("tNode_3_1" + i, "根节点三一" + i, "root", 2, "a", "node_3" + i);
			trees.add(tRoot);
			trees.add(tNode_1);
			trees.add(tNode_2);
			trees.add(tNode_3);
			trees.add(tNode_1_1);
			trees.add(tNode_1_2);
			trees.add(tNode_1_3);
			trees.add(tNode_2_1);
			trees.add(tNode_3_1);
			trees.add(tNode_1_1_1);
			trees.add(tNode_1_1_2);
			trees.add(tNode_1_1_3);
			trees.add(tNode_1_1_4);
			trees.add(tNode_1_1_4_1);
			trees.add(tNode_2_2);
			trees.add(tNode_2_3);
		}
		long total = testCount * 16;
		long start = System.currentTimeMillis();
		List list = resolveTree(trees);
		long middle = System.currentTimeMillis();
		System.out.println("解析" + total + "个节点消耗 [" + (middle - start) + "]毫秒！");
		String outStr = toJsonString(list);
		//System.out.println(outStr);
		long end = System.currentTimeMillis();
		System.out.println("打印" + total + "个节点消耗 [" + (end - middle) + "]毫秒！");

	}


	public static List<TreeNode> getSubNodes() {
		return null;
	}
}
